package sort

import (
	"math"
)

func RadixSort (arr []int) {
	if arr == nil || len(arr) < 2 {return}
	radixSort(arr, getDigit(arr))
}

func getDigit(arr []int ) int {
	max := arr[0]
	for i:=1; i<len(arr); i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}
	digit := 0
	for max != 0 {
		max = max/10
		digit++
	}
	return digit
}

func radixSort(arr []int, digit int) {
	radix := 10
	help := make([]int, len(arr))
	count := make([]int, radix)
	for location:=1; location<=digit; location++ {
		for j:=0; j<len(arr); j++ {
			count[getNumByLocation(arr[j], location)]++
		}
		for i:=1; i<len(count); i++{
			count[i] += count[i-1]
		}
		for i:=len(arr)-1; i>=0; i-- {
			NumCount := count[getNumByLocation(arr[i], location)]
			help[NumCount-1] = arr[i]
			count[getNumByLocation(arr[i], location)]--
		}
		for i:=0; i<len(arr); i++ {
			arr[i] = help[i]
		}
		count = make([]int, radix)
	}
}

func getNumByLocation(num int, location int) int {
	return num/int(math.Pow10(location-1)) % 10
}